package leetcode_600;

/**
 *@author 周杨
 *LongestPalindromicSubsequence_516 找出一个串中最长回文子序列
 *describe:用动态规划 AC 73%
 *2018年9月9日 下午4:51:03
 */
public class LongestPalindromicSubsequence_516 {
	
	public static void main(String[] args) {
		LongestPalindromicSubsequence_516 test=new LongestPalindromicSubsequence_516();
		System.out.println(test.longestPalindromeSubseq("cbbd"));
		System.out.println(test.longestPalindromeSubseq("bbbab"));
		System.out.println(test.longestPalindromeSubseq("b"));
	}
	 public int longestPalindromeSubseq(String s) {
	        if(s.length()==0)
	        	return 0;
	        char []chars=s.toCharArray();
	        int dp[][]=new int[s.length()][s.length()];
	        for(int i=0;i<s.length();++i) {//在以i为index的时候 往左遍历 始终维护一个局部max
	        	int max=1;
	        	dp[i][i]=1;
	        	for(int j=i-1;j>=0;--j) {
	        		if(chars[i]==chars[j]) {//如果有自然刷新
	        			if(i-j==1) {
	        				if(max<2) {
	        					max=2;
	        				}
	        			}
	        			else {
	        				if(max<2+dp[j+1][i-1])
	        					max=2+dp[j+1][i-1];
	        			}
	        			dp[j][i]=max;
	        		}
	        		else {//每次维护局部最优 和 当前去除原Index的最优
	        			dp[j][i]=Math.max(dp[j][i-1], max);
	        		}
	        	}
	        }
	        return dp[0][s.length()-1];
	 }
}
